package com.gqb.tree;

import java.util.ArrayDeque;
import java.util.Queue;



public class BinarySortTree {
	public static class Node {
		private int data;
		private String name;
		private Node leftNode;
		private Node rightNode;
		private Node parent;

		public Node(int data, Node parentNode) {
			super();
			this.data = data;
			this.parent = this.parent;
		}

		public Node(int data, String name) {
			super();
			this.data = data;
			this.name = name;
		}
		public Node(int data) {
			super();
			this.data = data;
		}
		public Node() {
		}
		public String getName() {
			return name;
		}
		public void setName(String name) {
			this.name = name;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}

		public Node getLeftNode() {
			return leftNode;
		}

		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}

		public Node getRightNode() {
			return rightNode;
		}

		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}

		public Node getParent() {
			return parent;
		}

		public void setParent(Node parent) {
			this.parent = parent;
		}
	}
	
	private Node root;
	
	public Node addNode(Node node){
		if(root==null){
			root=node;
		}else{
			Node parent=getNodeIndex(root, node.getData());
			node.parent=parent;
			if(parent.getData()>node.getData()){
				parent.leftNode=node;
			}else{
				parent.rightNode=node;
			}
		}
		
		return root;
	}
	
	private Node getNodeIndex(Node node,int data){
		if(data>=node.getData()){
			if(node.getRightNode()==null){
				return node;
			}else{
				return getNodeIndex(node.rightNode, data);
			}
		}else {
			if(node.getLeftNode()==null){
				return node;
			}else{
				return getNodeIndex(node.leftNode, data);
			}
		}
	}
	public void breadth(){
		Queue<Node> queue=new ArrayDeque<>();
		if(root!=null){
			queue.add(root);
			while(!queue.isEmpty()){
				Node node=queue.poll();
				if(node.leftNode!=null)
					queue.add(node.leftNode);
				if(node.rightNode!=null)
					queue.add(node.rightNode);
				System.out.print(node.getData()+"-");
			}
		}
	}
	public void middle(){
		if(root!=null){
			pMiddle(root);
		}
	}
	private void pMiddle(Node node){
		if(node!=null){
			if(node.leftNode!=null)
			{
				pMiddle(node.leftNode);
			}
			System.out.println(node.getData());
			if(node.rightNode!=null){
				pMiddle(node.rightNode);
			}
		}
	}
	
	public void delete(int data){
		if(root!=null){
			Node node=search(root, data);
			if(node.leftNode==null&node.rightNode==null){
				Node parentNode=node.parent;
				if(parentNode.leftNode.getData()==data){
					parentNode.leftNode=null;
				}else {
					parentNode.rightNode=null;
				}
			}
			if(node.leftNode==null){
				Node parentNode=node.parent;
				if(parentNode.leftNode.getData()==data){
					parentNode.leftNode=node.rightNode;
				}else {
					parentNode.rightNode=node.rightNode;
				}
			}
			if(node.rightNode==null){
				Node parenNode=node.parent;
				if(parenNode.leftNode.getData()==data){
					parenNode.leftNode=node.leftNode;
				}else{
					parenNode.rightNode=node.leftNode;
				}
			}
			//既有右子树，又有做子树
			if(node.rightNode!=null&node.leftNode!=null){
				Node preNode=findPreNode(node);
				Node preParentNode=preNode.parent;
				if(preParentNode.leftNode.getData()==preNode.getData()){
					preParentNode.leftNode=null;
				}else{
					preParentNode.rightNode=null;
				}
				preNode.rightNode=node.rightNode;
				node.rightNode.parent=preNode;
				preNode.leftNode=node.leftNode;
				node.leftNode.parent=preNode;
				Node parentNode=node.parent;
				parentNode.rightNode=preNode;
			}
		}
	}
	/**
	 * 查找某个点的前驱节点
	 * @param node
	 * @return
	 */
	private Node findPreNode(Node node){
		Node rightSonNode=node.leftNode;
		while(rightSonNode.rightNode!=null){
			rightSonNode=rightSonNode.rightNode;
		}
		return rightSonNode;
	}
	/**
	 * 从根节点开始查找节点
	 * @param node
	 * @param data
	 * @return
	 */
	public Node search(Node node,int data){
		
		if(data==node.getData())
			return node;
		if(data>node.getData()){
			if(node.rightNode!=null){
				return search(node.rightNode, data);
			}else{
				return null;
			}
				
		}else{
			if(node.leftNode!=null){
				return search(node.leftNode, data);
			}else{
				return null;
			}
		}
	}
	public static void main(String[] args) {
		BinarySortTree tree=new BinarySortTree();
		tree.addNode(new Node(5));
		tree.addNode(new Node(20));
		tree.addNode(new Node(10));
		tree.addNode(new Node(3));
		tree.addNode(new Node(8));
		tree.addNode(new Node(15));
		tree.addNode(new Node(30));
		tree.middle();
		tree.delete(20);
		tree.middle();
	}
}
